On the number of alignments of k sequences
Identifieur interne : 000871 ( Main/Exploration ); précédent : 000870; suivant : 000872On the number of alignments of k sequences
Auteurs : R. Griggs [États-Unis] ; P. Hanlon [États-Unis] ; M. Odlyzko [États-Unis] ; S. Waterman [États-Unis]Source :
- Graphs and Combinatorics [ 0911-0119 ] ; 1990-06-01.
Abstract
Abstract: Numerous studies by molecular biologists concern the relationships between several long DNA sequences, which are listed in rows with some gaps inserted and with similar positions aligned vertically. This motivates our interest in estimating the number of possible arrangements of such sequences. We say that ak sequence alignment of sizen is obtained by inserting some (or no) 0's intok sequences ofn 1's so that every sequence has the same length and so that there is no position which is 0 in allk sequences. We show by a combinatorial argument that for any fixedk≥1, the numberf(k, n) ofk alignments of lengthn grows like (c k ) n as n → ∞, wherec k = (21/k − 1) -k . A multi-dimensional saddle-point method is used to give a more precise estimate forf(k, n).
Url:
DOI: 10.1007/BF01787724
Affiliations:
Links toward previous steps (curation, corpus...)
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">On the number of alignments of k sequences</title><author><name sortKey="Griggs, R" sort="Griggs, R" uniqKey="Griggs R" first="R." last="Griggs">R. Griggs</name></author><author><name sortKey="Hanlon, P" sort="Hanlon, P" uniqKey="Hanlon P" first="P." last="Hanlon">P. Hanlon</name></author><author><name sortKey="Odlyzko, M" sort="Odlyzko, M" uniqKey="Odlyzko M" first="M." last="Odlyzko">M. Odlyzko</name></author><author><name sortKey="Waterman, S" sort="Waterman, S" uniqKey="Waterman S" first="S." last="Waterman">S. Waterman</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:5E94A11472D839409487ACA0C1C38F0B7F91B2BA</idno><date when="1990" year="1990">1990</date><idno type="doi">10.1007/BF01787724</idno><idno type="url">https://api.istex.fr/document/5E94A11472D839409487ACA0C1C38F0B7F91B2BA/fulltext/pdf</idno><idno type="wicri:Area/Main/Corpus">000641</idno><idno type="wicri:Area/Main/Curation">000641</idno><idno type="wicri:Area/Main/Exploration">000871</idno><idno type="wicri:explorRef" wicri:stream="Main" wicri:step="Exploration">000871</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">On the number of alignments of k sequences</title><author><name sortKey="Griggs, R" sort="Griggs, R" uniqKey="Griggs R" first="R." last="Griggs">R. Griggs</name><affiliation wicri:level="1"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Mathematics, University of South Carolina, 29208, Columbia, SC</wicri:regionArea><wicri:noRegion>SC</wicri:noRegion></affiliation></author><author><name sortKey="Hanlon, P" sort="Hanlon, P" uniqKey="Hanlon P" first="P." last="Hanlon">P. Hanlon</name><affiliation wicri:level="1"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Mathematics, Caltech, 91125, Pasadena, CA</wicri:regionArea><wicri:noRegion>CA</wicri:noRegion></affiliation></author><author><name sortKey="Odlyzko, M" sort="Odlyzko, M" uniqKey="Odlyzko M" first="M." last="Odlyzko">M. Odlyzko</name><affiliation wicri:level="1"><country xml:lang="fr">États-Unis</country><wicri:regionArea>AT&T Bell Laboratories, 07974, Murray Hill, NJ</wicri:regionArea><wicri:noRegion>NJ</wicri:noRegion></affiliation></author><author><name sortKey="Waterman, S" sort="Waterman, S" uniqKey="Waterman S" first="S." last="Waterman">S. Waterman</name><affiliation wicri:level="4"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Departments of Mathematics and Molecular Biology, University of Southern California, 90089, Los Angeles, CA</wicri:regionArea><orgName type="university">Université de Californie du Sud</orgName><placeName><settlement type="city">Los Angeles</settlement><region type="state">Californie</region></placeName></affiliation></author></analytic><monogr></monogr><series><title level="j">Graphs and Combinatorics</title><title level="j" type="abbrev">Graphs and Combinatorics</title><idno type="ISSN">0911-0119</idno><idno type="eISSN">1435-5914</idno><imprint><publisher>Springer-Verlag</publisher><pubPlace>Tokyo</pubPlace><date type="published" when="1990-06-01">1990-06-01</date><biblScope unit="volume">6</biblScope><biblScope unit="issue">2</biblScope><biblScope unit="page" from="133">133</biblScope><biblScope unit="page" to="146">146</biblScope></imprint><idno type="ISSN">0911-0119</idno></series><idno type="istex">5E94A11472D839409487ACA0C1C38F0B7F91B2BA</idno><idno type="DOI">10.1007/BF01787724</idno><idno type="ArticleID">BF01787724</idno><idno type="ArticleID">Art3</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0911-0119</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Numerous studies by molecular biologists concern the relationships between several long DNA sequences, which are listed in rows with some gaps inserted and with similar positions aligned vertically. This motivates our interest in estimating the number of possible arrangements of such sequences. We say that ak sequence alignment of sizen is obtained by inserting some (or no) 0's intok sequences ofn 1's so that every sequence has the same length and so that there is no position which is 0 in allk sequences. We show by a combinatorial argument that for any fixedk≥1, the numberf(k, n) ofk alignments of lengthn grows like (c k ) n as n → ∞, wherec k = (21/k − 1) -k . A multi-dimensional saddle-point method is used to give a more precise estimate forf(k, n).</div></front></TEI><affiliations><list><country><li>États-Unis</li></country><region><li>Californie</li></region><settlement><li>Los Angeles</li></settlement><orgName><li>Université de Californie du Sud</li></orgName></list><tree><country name="États-Unis"><noRegion><name sortKey="Griggs, R" sort="Griggs, R" uniqKey="Griggs R" first="R." last="Griggs">R. Griggs</name></noRegion><name sortKey="Hanlon, P" sort="Hanlon, P" uniqKey="Hanlon P" first="P." last="Hanlon">P. Hanlon</name><name sortKey="Odlyzko, M" sort="Odlyzko, M" uniqKey="Odlyzko M" first="M." last="Odlyzko">M. Odlyzko</name><name sortKey="Waterman, S" sort="Waterman, S" uniqKey="Waterman S" first="S." last="Waterman">S. Waterman</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Amerique/explor/CaltechV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000871 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000871 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Amerique
|area= CaltechV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:5E94A11472D839409487ACA0C1C38F0B7F91B2BA
|texte= On the number of alignments of k sequences
}}
| This area was generated with Dilib version V0.6.32. |  |